package edu.kmust.simple;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @author: 常伟
 * @create: 2019/3/12 21:25
 * @email: kmustchang@qq.com
 * @version: 1.0
 * @Description: 第二十题：寻找最大和，使用动态规划的方法
 *                          2
 *                       5     4
 *                    3     4     7
 *                 1     6     9     6
 *           最大和是：2，4，7，9的总和是22
 */
public class ExaminationTwenty01 {

    /**表示行数*/
    int row=4;
    /**表示所有的数字*/
    int[] number=new int[row*(row+1)<<1];
    /**表示某一个数字的前驱*/
    int[] path=new int[row*(row+1)<<1];
    /**表示某一行中的总和*/
    int[] totalSum=new int[row];
    /**表示最终的结果*/
    int[] result=new int[row];

    public static void main(String[] args) {
        ExaminationTwenty01 examinationTwenty01=new ExaminationTwenty01();
        examinationTwenty01.init();
        examinationTwenty01.completePath();
        System.out.println(Arrays.toString(examinationTwenty01.result));
    }

    private void completePath() {
        int base=0;
        for(int i=1;i<row;i++){
            int[] temp=new int[i+1];
            base+=i;
            for(int j=0;j<=i;j++){
                if(j==0){
                    temp[j]=totalSum[j]+number[j+base];
                    path[base+j]=base-i;
                }else if(i==j){
                    temp[j]=totalSum[j-1]+number[j+base];
                    path[base+j]=base-1;
                }else{
                    if(totalSum[j-1]>totalSum[j]){
                        temp[j]=number[j+base]+totalSum[j-1];
                        path[base+j]=base-i+j-1;
                    }else{
                        temp[j]=number[j+base]+totalSum[j];
                        path[base+j]=base-i+j;
                    }
                }
            }
            IntStream.range(0, i+1).forEach(k -> totalSum[k] = temp[k]);
        }
        int maxIndex=0;
        int max=totalSum[0];
        for(int i=1;i<row;i++){
            if(totalSum[i]>max){
                max=totalSum[i];
                maxIndex=i;
            }
        }
        maxIndex+=(row*(row-1)/2);
        for(int i=row-1;i>=0;i--){
            result[i]=number[maxIndex];
            maxIndex=path[maxIndex];
        }
    }

    /**
     * 这个表示初始化的内容
     */
    private void init() {
        number[0]=2;
        number[1]=5;
        number[2]=4;
        number[3]=3;
        number[4]=4;
        number[5]=7;
        number[6]=1;
        number[7]=6;
        number[8]=9;
        number[9]=6;
        //将第一个总和设置为第一个数字，即第一行的总和就是第一个数字
        totalSum[0]=number[0];
    }


}
